package com.banmao.algorithm.No1To100.No76;

public class Solution2 {

    public static String minWindow(String s, String t) {

        int sLen = s.length();
        int tLen = t.length();

        char[] sCharArray = s.toCharArray();
        char[] tCharArray = t.toCharArray();

        int[] tFreq = new int[128]; // t中字符出现的频数
        int[] winFreq = new int[128]; // 滑动窗口内字符出现的频数

        // 给t的频数数组赋值
        for (char c : tCharArray) {
            tFreq[c]++;
        }

        int left = 0, right = 0;
        int hamming_distance = 0; // 记录t的频数与滑动窗口内字符的相同个数

        int length = Integer.MAX_VALUE, resLeft = 0; // 最后结果的长度以及左指针坐标

        for(; right <= sLen - 1; right++) {

            // 将右指针指向的字符给winFreq赋值，如果其属于tFreq，则hamming_distance自增
            char rightChar = sCharArray[right];
            if(tFreq[rightChar] > winFreq[rightChar]) {
                // 右指针字符属于tFreq并且窗口内该字符个数不足
                hamming_distance++;
            }
            winFreq[rightChar]++;

            while(hamming_distance >= tLen) {

                printWindow(sCharArray, left, right);
                System.out.print(" A: " + winFreq['A']);
                System.out.print(" B: " + winFreq['B']);
                System.out.print(" C: " + winFreq['C']);
                System.out.print(" distance: " + hamming_distance + "\n");

                // 判断长度是否最小
                if(right - left + 1 < length) {
                    length = right - left + 1;
                    resLeft = left;
                }

                // 收缩左边界
                char leftChar = sCharArray[left];
                if(tFreq[leftChar] != 0 && tFreq[leftChar] == winFreq[leftChar]) {
                    hamming_distance--;
                }
                winFreq[leftChar]--;
                left++;

            }

        }

        if(length == Integer.MAX_VALUE) {
            return "";
        }

        return s.substring(resLeft, resLeft + length);
    }

    private static void printWindow(char[] sCharArray, int left, int right) {

        StringBuilder sb = new StringBuilder("[");
        for(; left <= right; left++) {
            sb.append(sCharArray[left] + ", ");
        }
        sb.replace(sb.length() - 2, sb.length() - 1, "]");
        //sb.append("]");
        System.out.println(sb);
    }

    public static void main(String[] args) {
        String a = "ABCDEF";
        printWindow(a.toCharArray(), 2, 4);
    }

}
